import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        elem = new int[10];
    }

    // 将数组变成大根堆结构
    public void createHeap(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            usedSize++;
        }
        // 得到根节点parent, parent--依次来到每颗子树的根节点，
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            // 依次向下搜索，使得每颗子树都变成大根堆
            shiftDown(parent,usedSize);
        }
    }
    // 向下搜索变成大根堆
    public void shiftDown(int parent,int len){
        int child = parent*2+1;// 拿到左孩子
        while (child < len){
            // 如果有右孩子,比较左右孩子大小,得到较大的值和父节点比较
            if (child+1 < len && (elem[child] < elem[child+1])){
                child++;
            }
            // 比较较大的孩子和父节点,看是否要交换
            int max = elem[parent] >= elem[child] ? parent : child;
            if (max == parent) break;// 如果不需要调整了，说明当前子树已经是大根堆了，直接 break
            swap(elem,parent,child);
            parent = child;// 继续向下检测，看是否要调整
            child = parent*2+1;
        }
    }
    // 添加一个元素后，将其再变成大根堆
    public void offer(int num){
        if (usedSize == elem.length){
            // 扩容
            elem = Arrays.copyOf(elem,elem.length + (elem.length >> 1));
        }
        elem[usedSize++] = num;
        shiftUp(usedSize-1);
    }

    // 向上搜索，使每颗子树变成大根堆
    public void shiftUp(int child) {
        int parent = (child-1)/2;
        while (child != parent){
            if (elem[child] > elem[parent]){
                swap(elem,parent,child);
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

    public int poll(){
        if (usedSize == 0) throw new RuntimeException("优先级队列为空！");
        int temp = elem[0];
        swap(elem,0,--usedSize);
        shiftDown(0,usedSize);
        return temp;
    }
    public void heapSort(){
        int len = usedSize;
        while (len > 1){
            swap(elem,0,--len);
            shiftDown(0,len);
        }
    }

    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
